package com.easy;

/**
 * Created by Lxk on 2019/6/10.
 */
public class Solution561 {

    private int partion(int[] arr,int lo,int hi){
        int i = lo,k = hi+1;
        int v = arr[lo];
        while(true){
            while(arr[++i]<v)
                if(i==hi){
                    break;
                }
            while(arr[--k]>v)
                if(k==lo){
                    break;
                }
            if(i>=k){
                    break;
            }
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
        int temp = arr[lo];
        arr[lo] = arr[k];
        arr[k] = temp;
        return k;
    }

    private void sort(int[] arr,int lo,int hi){
        if(hi<=lo){
            return ;
        }
        int k = partion(arr,lo,hi);
        sort(arr,lo,k-1);
        sort(arr,k+1,hi);
    }

    public int arrayPairSum(int[] nums) {
        if(nums==null ||nums.length==0){
            return 0;
        }
        sort(nums,0,nums.length-1);
        int sum = 0;
        for(int i = 0;i < nums.length; i+=2){
            sum += nums[i];
        }
        return sum;
    }

}
